//柠檬水找零
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int dollar[2]{0,0}; // 10 5
        for(size_t i = 0 ; i < bills.size() ; ++i)
        {
            if(bills[i] == 5) dollar[1]++;
            else if(bills[i] == 10)
            {
                dollar[0]++;
                dollar[1]--;
            }
            else
            {
                if(dollar[0] > 0)
                {
                    dollar[0]--;
                    dollar[1]--;
                }
                else 
                {
                    dollar[1]-=3;
                }
            }
            if(dollar[0] < 0 || dollar[1] < 0) return false;
        }
        return true;
    }
};

//将数组和减半的最小操作次数
class Solution {
public:
    int halveArray(vector<int>& nums) {
        double sum = 0;
        priority_queue<double> pq;
        for(auto e : nums)
        {
            sum += e;
            pq.push(e);
        }
        double dst = sum / 2.0;
        int ret = 0;
        while(sum > dst)
        {
           double temp = pq.top();
           pq.pop();
           temp /= 2.0;
           sum -= temp;
           pq.push(temp);
           ++ret; 
        }
        return ret;
    }
};

//最大数
class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> str;
        for(auto& e : nums)
        {
            str.push_back(to_string(e));
        }
        sort(str.begin() , str.end(),[](string& num1,string& num2){
            return num1+num2 > num2+num1;
        });
        string ret;
        for(auto& e : str)
        {
            ret += e;
        }
        if(ret[0] == '0') return "0";
        return ret;
    }
};

//摆动序列
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        //双指针控制区间
        if(nums.size() == 1) return 1;
        int m = nums.size();
        int ret = 0;
        int left = 0 , right = 0;
        for(size_t i = 0 ; i < m ; ++i)
        {
            while(i < m - 1 && nums[i] == nums[i+1]) ++i;
            if(i == m-1) right = 0;
            else right = nums[i+1] - nums[i];

            if(static_cast<long long>(left) * right <= 0) ret++;
            left = right;
        }
        return ret;
    }
};

//最长递增子序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //贪心解
        vector<int> v;
        int n = nums.size();
        v.push_back(nums[0]);
        for(size_t i = 1 ; i < n ; ++i)
        {
            int left = 0 , right = v.size() - 1;
            int target = nums[i];
            int mid = 0;
            while(left <= right)
            {
                mid = left + (right - left)/2;
                if(target > v[mid]) left = mid + 1;
                else if(target < v[mid]) right = mid - 1;
                else break;
            }
            if(left <= right) continue;
            else
            {
                if(left == v.size()) v.push_back(target);
                else v[left] = target;
            }
        }
        return v.size();
    }
};